package com.hqq.stack;

import com.hqq.stack.exception.StackEmptyException;
import com.hqq.stack.exception.StackFullException;

import java.util.Iterator;

/**
 * LinkedListStack
 * 栈的链表实现法
 * 使用带头结点的链表
 * Created by heqianqian on 2017/8/3.
 */
public class LinkedListStack<T> implements Stack<T> {

    /**
     * 栈顶节点
     */
    private Node<T> head;

    /**
     * 栈中元素个数
     */
    private int count;

    public LinkedListStack() {
        head = new Node<>(null);
    }

    @Override
    public void push(T t) throws StackFullException {
        this.getTailNode().next = new Node<>(t);
        count++;
    }

    @Override
    public T pop() throws StackEmptyException {
        Node<T> tailPreviousNode = getTailPreviousNode();
        Node<T> top = tailPreviousNode.next;
        tailPreviousNode.next = null;//便于GC回收
        count--;
        return top.data;
    }

    @Override
    public T top() {
        return getTailNode().data;
    }

    @Override
    public boolean isEmpty() {
        return head.next == null;
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListStackIterator<>(this);
    }

    /**
     * 返回栈顶元素的前一个元素
     */
    private Node<T> getTailPreviousNode() {
        Node<T> temp = head;
        while (temp.next.next != null) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 返回栈顶元素
     */
    private Node<T> getTailNode() {
        Node<T> temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 链表节点
     */
    private class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    /**
     * 迭代器
     */
    private class LinkedListStackIterator<T> implements Iterator<T> {

        private LinkedListStack<T> linkedListStack;

        private Node<T> node;

        @SuppressWarnings("unchecked")
        public LinkedListStackIterator(LinkedListStack<T> linkedListStack) {
            this.linkedListStack = linkedListStack;
            node = (Node<T>) this.linkedListStack.head;
        }

        @Override
        public boolean hasNext() {
            return !(this.node.next == null);
        }

        @Override
        public T next() {
            Node<T> node = this.node.next;
            this.node = this.node.next;
            return node.data;
        }
    }
}
